搜索引擎实现¶


使用 Golang + Redis¶

CPT2406170835-640x591.gif

爬虫¶


并发的dfs ,发送Get请求 获取html内容¶
❗❗ 网站之间的链接不是 有向无环图¶
❗❗ 相对链接的处理¶
In [ ]:
func dfs(url string) {
	if visited[url]     return  //visted
	visited[url] = true 

	resp:= http.Get(url)

	for _, link := range links {
		// 相对 -> 绝对
		if !strings.HasPrefix(link, "http") 
			link = url + link
		
		go dfs(link)
	}
}

减少心智负担的选择¶

http库复杂header,cookie的设置¶
各种并发锁(性能)¶
难以解析(设计复杂的正则表达式)👎👎¶

Colly 是一个用于 Web 数据抓取和爬虫的 Go 语言框架。✔

  1. 并发支持
  2. 简单易用
  3. 更好的抽象

image.png

倒排索引的实现¶


In [ ]:
1: you are a good boy ha ha o yeah
2: o my god you like bleach naruto one piece and so do i
3: but i do not think you will get all the points

you     :   [1,2,3]
i       :   [2,3]
all     :   [3]

索引的数据结构¶

👉 Map

map[word].append(html_id)

每扫到一个单词就在 map[word] 列表中插入该网页的id

2. trie 树¶

struct {
    int cnt = 0;
    int child[26] = {0};
}trie_node[10010];

void find(char str[]){
    int ptr = 0; 
    for(int i = 0 ; str[i] ; i++){
        if child not exist 
            ptr = node[ptr].lchild;
    }
    return cnt;  
}

void insert(char str[]){
    int ptr = 0;

    for(int i = 0 ; str[i] ; i++){
        int num = str[i] - 'a'; //映射
        if( !trie_node[ptr].child[num] ){   
            trie_node[ptr].child[num] = ++idx;
        }
        ptr = trie_node[ptr].child[num];  // ptr = node[ptr].lchild;
    }
    trie_node[ptr].cnt++;   //标记 

}

合并索引¶


$ 返回\quad A \cap B \cap C \cap \ldots$¶

分治¶


  • 两个有序列表合并为一个有序列表(取交集)
  • 类似分治排序中的merge操作
In [ ]:
for i < len_arr && j < len_brr {
    if arr[i] == brr[j] {
        ans = append(ans, arr[i])
        i += 1
        j += 1
    } else if arr[i] < brr[j] {
        i += 1
    } else if arr[i] > brr[j] {
        j += 1
    }
}

⚠️ 并发¶


  • 分治算法容易设计为并发
In [ ]:
func merge_index(str []string, l int, r int) []int {
    if l == r  str[l]
	
    mid = (l + r) / 2
	
    go  merge_index(str, l, mid)
    go  merge_index(str, mid+1, r)

    return merge(l_list, r_list)

}

Redis¶


  • Redis是一个开源的内存键值对存储系统
  1. 存储在内存中,高性能, 也支持将数据持久化到硬盘上
  2. Redis支持多种原子性操作
  3. 事务支持,允许一组操作作为一个原子操作进行执行

Golang¶


  • 简洁易学,强大的并发支持,垃圾回收
  • 丰富生态,许多优秀的第三方库和工具
  • GDB/LLDB 支持度不完善,delve没学 调试全靠猜😰